package com.lx.algorithm.slidWindow;

import java.util.LinkedList;

import static com.lx.algorithm.quickSort.PartitionAndQuickSort.generateRandomArray;
import static com.lx.algorithm.quickSort.PartitionAndQuickSort.isEqual;
import static com.lx.algorithm.radix.RadixSort.printArray;

/**
 * Description:
 * Copyright:   Copyright (c)2019
 * Company:     zefu
 *
 * @author: 张李鑫
 * @version: 1.0
 * Create at:   2021-11-15 15:28:20
 * <p>
 * Modification History:
 * Date         Author      Version     Description
 * ------------------------------------------------------------------
 * 2021-11-15     张李鑫                     1.0         1.0 Version
 */
public class MaxValue {


    /**
     * 假设一个固定大小为W的窗口，依次划过arr，
     * 返回每一次滑出状况的最大值
     * 例如，arr = [4,3,5,4,3,3,6,7], W = 3
     * 返回：[5,5,5,4,6,7]
     */

    // 暴力的对数器方法
    public static int[] right(int[] arr, int w) {
        if (arr == null || w < 1 || arr.length < w) {
            return null;
        }
        int N = arr.length;
        int[] res = new int[N - w + 1];
        int index = 0;
        int L = 0;
        int R = w - 1;
        while (R < N) {
            int max = arr[L];
            for (int i = L + 1; i <= R; i++) {
                max = Math.max(max, arr[i]);

            }
            res[index++] = max;
            L++;
            R++;
        }
        return res;
    }

    /**
     * 获取每次活动的窗口最大值
     *
     * @param arr
     * @param w
     * @return
     */
    public static int[] getMaxWindow(int[] arr, int w) {
        if (arr == null || w < 1 || arr.length < w) {
            return null;
        }
        //返回的数组长度是 原来数组的个数-w+1
        int resultLength = arr.length + 1 - w;
        //创建返回数组
        int[] result = new int[resultLength];
        //创建双端队列
        LinkedList<Integer> list = new LinkedList<>();
        //返回值的指针
        int resultIndex = 0;
        //最开始的过期索引
        int over = -w;
        for (int i = 0; i < arr.length; i++) {
            //每次循环进来说明已经前进了一个格子 所以先+失效索引的
            over++;
            //如果list不为空 并且新来的这个数字大于最后的值 就弹出 一直弹出 弹到不能弹为止
            while (!list.isEmpty() && arr[list.getLast()] < arr[i]) {
                list.pollLast();
            }
            //加入最新的索引值
            list.add(i);
            //如果over为正了 才开始计算最大值
            if ((over >= 0) && resultIndex < result.length) {
                result[resultIndex++] = arr[list.getFirst()];
            }
            //计算当前索引的过期指针 如果over跟第一个指针的索引相等 说明他过期了 把他弹掉
            if (over == list.getFirst()) {
                list.pollFirst();
            }

        }
        return result;
    }

    public static void main(String[] args) {
        int testTime = 100000;
        int maxSize = 100;
        int maxValue = 100;
        System.out.println("test begin");
        for (int i = 0; i < testTime; i++) {
            int[] arr = generateRandomArray(maxSize, maxValue);
            int w = (int) (Math.random() * (arr.length + 1));
            int[] ans1 = getMaxWindow(arr, w);
//            int[] ans1 = getMaxWindow(arr, w);
            int[] ans2 = right(arr, w);
            if (!isEqual(ans1, ans2)) {
                printArray(arr);
                System.out.println("Oops!");
                break;
            }
        }
        System.out.println("test finish");
    }

}
